package ru.nsu.ccfit.shumkina.algorithm.adaptation;

import ru.nsu.ccfit.shumkina.algorithm.graphworks.Graph;
import ru.nsu.ccfit.shumkina.algorithm.graphworks.Page;
import ru.nsu.ccfit.shumkina.algorithm.world.Settings;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: Вера
 * Time: 3:21
 * To change this template use File | Settings | File Templates.
 */
public class Algorithm {
    public Settings settings;
    public TreeMap<String, UsedPathsInfo> usedPaths;

    public TreeMap<String, String> acceptedAdaptations;
    public Graph adaptedMenuGraph;

    private AlgorithmSubgraph subMenu;
    private String currentMainPage;
    private TreeMap<String, String> previousMainPages;
    private TreeMap<String, Integer> possibleArcs;
    private TreeMap<String, String> usedChildren;
    private AdaptationRecord currentRecord;


    public void makeAdaptations(){
        acceptedAdaptations = new TreeMap<String, String>();
        TreeSet<Map.Entry<String, UsedPathsInfo>> usedPathsEntries =
                new TreeSet<Map.Entry<String, UsedPathsInfo>>(new Comparator<Map.Entry<String, UsedPathsInfo>>() {
            @Override
            public int compare(Map.Entry<String, UsedPathsInfo> o1, Map.Entry<String, UsedPathsInfo> o2) {
                return o2.getValue().startPageIdUseCount - o1.getValue().startPageIdUseCount;
            }
        });

        for (Map.Entry<String, UsedPathsInfo> entry: usedPaths.entrySet())
        {
            usedPathsEntries.add(entry);
        }
         // for every start page
        for (Map.Entry<String, UsedPathsInfo> entry: usedPathsEntries)
        {
            // build subgraph with current use
            subMenu = new AlgorithmSubgraph();
            previousMainPages = new TreeMap<String, String>();
            if (!adaptedMenuGraph.pages.containsKey(entry.getKey()))
                continue; //current start page not in the menu
            ExtendedPage mainPage = new ExtendedPage(entry.getKey());
            mainPage.visitCount = 0;
            mainPage.rootDistance = 0;
            
            mainPage.itemsLeft = countItemsLeft(mainPage.pageId);
            mainPage.symbolsLeft = countSymbolsLeft(mainPage.pageId);
            subMenu.treeRoots.add(mainPage);
            subMenu.pages.put(mainPage.pageId, mainPage);
            for (Map.Entry<String, Path> pathEntry: entry.getValue().paths.entrySet())
            {
                ExtendedPage prev = null;
                for (String node: pathEntry.getValue().path)
                {
                    if (!subMenu.pages.containsKey(node))
                    {
                        ExtendedPage page = new ExtendedPage(node);
                        page.visitCount = pathEntry.getValue().useCount;
                        if (prev == null)
                            page.rootDistance = 0;
                        else
                            page.rootDistance = prev.rootDistance +1;

                        page.itemsLeft = countItemsLeft(node);
                        page.symbolsLeft = countSymbolsLeft(node);

                        subMenu.pages.put(node, page);

                        if (prev != null)
                        {
                            prev.children.put(node, page);
                            page.parents.put(prev.pageId, prev);
                            subMenu.arcNames.put(prev.pageId + " -> " + page.pageId, page.pageId);
                        }

                        prev = page;
                    }
                    else
                    {
                        ExtendedPage page = subMenu.pages.get(node);
                        page.visitCount += pathEntry.getValue().useCount;
                        prev = page;
                    }
                }
            } // subgraph building ended

            // go down throw the graph pages
            while (!subMenu.treeRoots.isEmpty())
            {
                //System.out.print("Current main page "+entry.getKey()+". Current v "+currentMainPage + "\n");
                currentMainPage = subMenu.treeRoots.get(0).pageId;
                subMenu.treeRoots.remove(0);

                if (!previousMainPages.containsKey(currentMainPage))
                    adaptCurrentMainPage();

            }
        }
    }

    private void adaptCurrentMainPage() {
        ExtendedPage mp = subMenu.pages.get(currentMainPage);
        previousMainPages.put(currentMainPage, currentMainPage);
        if (mp.itemsLeft == 0)
            return;
        //generate all possible new arcs
        possibleArcs = new TreeMap<String, Integer>();
        //recursion
        usedChildren = new TreeMap<String, String>();
        maxProfit1 =0;
        maxProfit2 =0;
        maxProfit3 =0;
        maxProfitLength1 = 9999;
        maxProfitLength2 = 9999;
        maxProfitLength3 = 9999;
        {
        for (Map.Entry<String, ExtendedPage> kid: mp.children.entrySet())
        {
            generateArcs(kid.getValue());
        }
        if (possibleArcs.isEmpty())
            return;

        // get best subset
        TreeMap<String, Integer> subset = new TreeMap<String, Integer>();
        currentRecord = new AdaptationRecord();

        Integer symbols = 0;
        if (maxProfit1 != 0)
        {
            subset.put(maxString1, possibleArcs.get(maxString1));
            symbols += maxString1.length();
            if (maxProfit2 != 0 && mp.itemsLeft > 1 && mp.symbolsLeft - symbols >= maxString2.length())
            {
                subset.put(maxString2, possibleArcs.get(maxString2));
                symbols += maxString2.length();
            }
            if (maxProfit3 != 0 && mp.itemsLeft > subset.size() && mp.symbolsLeft - symbols >= maxString3.length())
            {
                subset.put(maxString3, possibleArcs.get(maxString3));
                symbols += maxString3.length();
            }
        }
        if (mp.symbolsLeft - symbols >0 && mp.itemsLeft > subset.size())
        {
            for (Map.Entry<String, Integer> arc: possibleArcs.entrySet())
            {
                if (subset.containsKey(arc.getKey()))
                    generateSubsetOfArcs(subset, mp.itemsLeft - subset.size());
                else
                {
                    subset.put(arc.getKey(), arc.getValue());
                    generateSubsetOfArcs(subset, mp.itemsLeft - subset.size());
                    subset.remove(arc.getKey());
                }
            }
        }
            else {
            generateSubsetOfArcs(subset, 0);
        }
        // work with record
        applyRecordAdaptation();
        }
        // add kids as next Main Pages
        for(Map.Entry<String, ExtendedPage> k: mp.children.entrySet())
        {
            if (previousMainPages.containsKey(k.getKey()))
                continue;

            if (k.getValue().children.isEmpty())
                continue;

            subMenu.treeRoots.add(k.getValue());
        }

    }

    private void applyRecordAdaptation() {
        for (String currentArc :currentRecord.arcs)
        {
            String[] pages = currentArc.split(" -> ");
            Page pageFrom = adaptedMenuGraph.pages.get(pages[0]);
            Page pageTo = adaptedMenuGraph.pages.get(pages[1]);

            pageFrom.children.put(pageTo.pageId, pageTo);
            pageTo.parents.put(pageFrom.pageId, pageFrom);
            adaptedMenuGraph.arcNames.put(pageFrom.pageId + " -> " + pageTo.pageId, pageTo.pageId);

            acceptedAdaptations.put(pageFrom.pageId + " -> " + pageTo.pageId, pageTo.pageId);
        }
    }

    private void generateSubsetOfArcs(TreeMap<String, Integer> subset, int elementsLeft) {
        if (elementsLeft == 0)
        {
            Integer profit = 0;
            Integer symbols = 0;
            for (Map.Entry<String, Integer> arc: subset.entrySet())
            {
                profit += arc.getValue();
                symbols += arc.getKey().length() - currentMainPage.length() - 4; // 4 for " -> "
            }
            if (profit < currentRecord.profit)
                return;

            // check constraints
            if (subMenu.pages.get(currentMainPage).symbolsLeft < symbols)
                return;

            if (profit == currentRecord.profit && currentRecord.arcs.size() <= subset.size())
                return;

            // change record
            currentRecord.profit = profit;
            currentRecord.arcs.clear();
            for (Map.Entry<String, Integer> arc: subset.entrySet())
            {
                currentRecord.arcs.add(arc.getKey());
            }
            return;
        }
        for (Map.Entry<String, Integer> arc: possibleArcs.entrySet())
        {
            if (subset.containsKey(arc.getKey()))
                generateSubsetOfArcs(subset, elementsLeft - 1);
            else
            {
                subset.put(arc.getKey(), arc.getValue());
                generateSubsetOfArcs(subset, elementsLeft - 1);
                subset.remove(arc.getKey());
            }
        }
       //System.out.print(String.valueOf(elementsLeft) + "\n");
    }

    Integer maxProfit1 = 0; Integer maxProfitLength1 = 9999;
    Integer maxProfit2 = 0; Integer maxProfitLength2 = 9999;
    Integer maxProfit3 = 0; Integer maxProfitLength3 = 9999;
    String maxString1 ="";
    String maxString2 = "";
    String maxString3 = "";

    private void generateArcs(ExtendedPage value) {
        for (Map.Entry<String, ExtendedPage> k: value.children.entrySet())
        {
            if (usedChildren.containsKey(k.getKey()))
                continue;
            // arcs generation
            if (subMenu.pages.get(currentMainPage).symbolsLeft >= k.getKey().length())
            {
                // check if arc already present in menu
                if (!adaptedMenuGraph.arcNames.containsKey(currentMainPage + " -> " + k.getKey()))
                {
                    Integer possibleProfit = (k.getValue().rootDistance -
                            subMenu.pages.get(currentMainPage).rootDistance)*k.getValue().visitCount;
                    if (possibleProfit <= maxProfit3 && k.getKey().length() >= maxProfitLength3)
                        ; //should reduce possible arcs
                    else if (possibleProfit > 0)
                    {
                            possibleArcs.put(currentMainPage + " -> " + k.getKey(), possibleProfit);
                        if (possibleProfit > maxProfit1)
                        {
                            maxProfit3 = maxProfit2;
                            maxProfitLength3 = maxProfitLength2;
                            maxString3 = maxString2;
                            maxProfit2 = maxProfit1;
                            maxProfitLength2 = maxProfitLength1;
                            maxString2 = maxString1;
                            maxProfit1 = possibleProfit;
                            maxProfitLength1 = k.getKey().length();
                            maxString1 = currentMainPage + " -> " + k.getKey();
                        }
                        else if (possibleProfit > maxProfit2)
                        {
                            maxProfit3 = maxProfit2;
                            maxProfitLength3 = maxProfitLength2;
                            maxString3 = maxString2;
                            maxProfit2 = possibleProfit;
                            maxProfitLength2 = k.getKey().length();
                            maxString2 = currentMainPage + " -> " + k.getKey();
                        }
                        else if (possibleProfit > maxProfit3)
                        {
                            maxProfit3 = possibleProfit;
                            maxProfitLength3 = k.getKey().length();
                            maxString3 = currentMainPage + " -> " + k.getKey();
                        }
                    }

                }
            }

            // marked used
            usedChildren.put(k.getKey(), k.getKey());

            // go deeper
            generateArcs(k.getValue());
        }
    }

    private int countSymbolsLeft(String pageId) {
        int num = settings.getLatinPageSymbolsMax();
        for (Map.Entry<String, Page> p: adaptedMenuGraph.pages.get(pageId).children.entrySet())
        {
             num = num - p.getKey().length();
        }
        if (num < 0)
            num = 0;
        return num;  //To change body of created methods use File | Settings | File Templates.
    }

    private int countItemsLeft(String pageId) {
        int num = settings.getItemsPerPageMax() - adaptedMenuGraph.pages.get(pageId).children.size();
        if (num < 0)
            num = 0;
        return num;  //To change body of created methods use File | Settings | File Templates.
    }
}
